1. Field of the Invention
The present invention relates to a group signature system, a device, and a program, and for example, to a group signature system, a device, and a program in which a calculation amount is reduced and calculation speed is improved.
2. Description of the Related Art
A group signature scheme is proposed by Chaum et al. in 1991 as an electronic signature having anonymity (refer to D. Chaum and E. van Heyst, “Group Signatures,” In Proc. of EUROCRYPT '91, LNCS 547, pp. 257-265, 1998). Generally, in an electronic signature scheme, since one public key for signature verification corresponds to one secret key for signature generation, the anonymity of a signature generator cannot be protected.
Meanwhile, since one group public key for signature verification corresponds to n member secret keys for signature generation in a group signature scheme, the anonymity of a signature generator can be protected. That is, since one group public key corresponds to n member secret keys in the group signature scheme, brought about is the characteristic that the signature generator cannot be specified at the time of signature verification. In addition, the group signature system is characterized in that only a group manager serving as a privileged person can specify a signer.
However, since a signature length and a signature generation calculation amount are proportional to the number of members in the original group signature scheme, its efficiency in a group having many members is very low, thus it is not suitable for practical use.
In response, a group signature scheme with an efficiency unaffected by the number of members was proposed by Camenisch et al. in 1997 (refer to J. Camenisch and M. Stadler, “Efficient group signature schemes for large groups,” In Proc. of CRYPTO '97, LNCS 1294, pp. 410-424, 1997). In this scheme, the signature of a group manager for a member secret key is used as a membership certificate. A group signature includes a membership certificate (or a part thereof) encrypted with a public key of the group manager, and a non-interactive knowledge proof showing that the membership certificate is correctly encrypted and that the member secret key and the membership certificate are retained. A signature verifier can verify, by verifying the non-interactive knowledge proof, that the signature is made by the member. Furthermore, the group manager can specify the signer by decrypting the membership certificate. The concept that utilizes the membership certificate is important because it provides the basis for the following group signature scheme.
However, while the efficiency does not depend on the number of members in the scheme proposed by Camenisch et al., the efficiency is still low from a practical viewpoint.
The first practical group signature scheme was proposed by Ateniese et al. in 2000 (refer to G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik, “A practical and provably secure coalition-resistant group signature scheme,” In Proc. of CRYPTO 2000, LNCS 1880, pp. 255-270, 2000, which is referred to as the [ACJT00] scheme hereinafter). The group signature scheme of Ateniese is highly efficient, thus can be evaluated for its practical application. However, since the group signature scheme of Ateniese requires, at the time of signature generation, a calculation amount about 200 times that in RSA signature, improvements have continually been made. Security in the scheme of Ateniese is based on the strong-RSA problem.
A well-known high-speed group signature scheme at present is a scheme proposed by Camenisch in 2004 (refer to J. Camenisch and J. Groth, “Group Signatures: Better Efficiency and New Theoretical Aspects,” Forth Int. Conf. on Security in Communication Networks—SCN 2004, LNCS 3352, 120-133, 2005, which is referred to as the [CG04] scheme hereinafter. The full paper is available from the following URL; http://www.brics.dk/jg/ (as of June, 2007)). In the [CG04] scheme, the calculation amount for signature generation is reduced to about eight times that in RSA signature generation. The security of the [CG04] scheme is also based on the strong-RSA problem.